#!/usr/bin/env python
# -*- coding: utf-8 -*-

import tool_misc as tm

class Sequence :
  label_start = 0
  label_end = 1

  def __init__(self, l):
    self.ts = Tool_sequencing()
    self.list_intervals = l

  def get_list_vals(self) :
    res = []
    for interval in self.list_intervals :
      res.append((interval[0], self.label_start))
      res.append((interval[1], self.label_end))
    return res

  def sort_list_vals(self) :
    list_vals = self.get_list_vals()
    k = range(len(list_vals))
    def cmp_val(x,y) :
      return cmp(list_vals[x],list_vals[y])
    k.sort(cmp_val)
    return k

  def add_interval(self,interval) :
    self.list_intervals.append(interval)

  def __repr__(self):
    return repr(self.get_list_vals())

  def __str__(self):
    return str(self.list_intervals)

  def __add__(self, other) :
    l = self.list_intervals + other.list_intervals
    return Sequence(l)

  def __iadd__(self, other) :
    return self + other

  def __or__(self, other) :
    l = self + other
    return l.union()

  def __ior__(self,other) :
    return self | other

  def __and__(self, other) :
    u = self.union() + other.union()
    i = u.intersections()
    if 2 in i : return Sequence(i[2])
    return Sequence([])

  def __iand__(self,other) :
    return self & other

  def __mod__(self, other) :
    l1 = self.union().list_intervals
    l2 = other.union().list_intervals
    l = self.ts.filter_seq(l2, l1)
    return Sequence(l)

  def union(self) :
    l = self.get_list_vals()
    sort_list_val = self.sort_list_vals()

    union = []
    tampon = None
    cpt = 0
    for i in sort_list_val :
      val,tag = l[i]
      if(tag == self.label_start) :
        cpt +=1
        if(tampon == None) :
          tampon = val
      else :
        cpt -= 1
        if(cpt == 0) :
          union.append((tampon, val))
          tampon = None
    return Sequence(union)

  def intersections(self) :
    l = self.get_list_vals()
    sort_list_val = self.sort_list_vals()
    layer,stack = {},{}
    cpt = 0
    for i in sort_list_val :
      val,tag = l[i]
      if(tag == self.label_start) :
        cpt += 1
        if(stack.has_key(cpt) == False or (stack.has_key(cpt) and stack[cpt] == None)) :
          stack[cpt] = val
      else :
        tm.dict_append(layer, cpt, (stack[cpt], val))
        stack[cpt] = None
        cpt -= 1
    return layer

class Tool_sequencing :
  def __init__(self):
    self.list_sequences = []
    self.list_tags = []

  def fusion_list_val(self) :
    l = [] 
    for i,list_val in enumerate(self.list_sequences) :
      for j,val  in enumerate(list_val) :
        l.append((i,j,0))
        l.append((i,j,1))
    return l

  def sort_l(self, l):
    k = range(len(l))
    def cmp_val(x,y) :
      coord1 = l[x]
      coord2 = l[y]
      v1 = self.list_sequences[coord1[0]][coord1[1]][coord1[2]]
      v2 = self.list_sequences[coord2[0]][coord2[1]][coord2[2]]
      return cmp((v1,coord1[2]),(v2,coord2[2]))
    k.sort(cmp_val)
    return k

  def add_sequence(self, sequence, tag) :
    '''sequence = [(0,10), (14,33), (45,46)], tag = ('[',']')'''
    self.list_sequences.append(sequence)
    self.list_tags.append(tag)

  def filter_seq(self, seq1, seq2) :
    self.__init__()
    self.list_sequences = [seq1, seq2]
    self.list_tags = [('[',']'),('{','}')]
    return self.interseq()

  def interseq(self) :
    l = self.fusion_list_val()
    sort = self.sort_l(l)
    stack_tag, stack_i, list_res = [], [], []
    tag_src, tag_tgt = self.list_tags
    to_be_closed = []
    for i in sort :
      id_seq, id_int, order_tag = l[i]
      offset = self.list_sequences[id_seq][id_int][order_tag]
      tag = self.list_tags[id_seq]
      if order_tag == 0  :
        stack_tag.append(tag)
        stack_i.append(i)
      else :
        idx = tm.pop_val_id(stack_tag,tag)
        if(idx != -1) :
          j = stack_i[idx]
          id_seq2, id_int2, order_tag2 = l[j]
          start = self.list_sequences[id_seq2][id_int2][order_tag2]
          stack_tag = stack_tag[:idx] + stack_tag[idx+1:]
          stack_i = stack_i[:idx] + stack_i[idx+1:]

        if(tag == tag_src) :
          if (tag_tgt in stack_tag) :
            for idx,_ in enumerate(stack_tag) :
              to_be_closed.append(stack_i[idx])

        else :
          if(to_be_closed != []) :
            tbc = to_be_closed.pop() 
            tbc_seq, tbc_int, tbc_order_tag = l[tbc]
            start = self.list_sequences[tbc_seq][tbc_int][tbc_order_tag]
            list_res.append((start,offset))
          elif(tag_src in stack_tag) :
            list_res.append((start,offset))
    return list_res

  def segment_multitag_list(self) :
#    print self.list_sequences
    l = self.fusion_list_val()
#    print l
    sort = self.sort_l(l)
    stack = []
    list_res = []
    for i in sort :
      id_seq, id_int, order_tag = l[i]
      offset = self.list_sequences[id_seq][id_int][order_tag]
      tag = self.list_tags[id_seq]
      len_stack = len(stack)
      res = ''
      for i in xrange(len_stack) :
        res += stack[len_stack-i-1][1]
      if(order_tag == 0) :
        stack.append(tag)
      else :
        stack = tm.pop_val(stack,tag)
      for val in stack :
        res += val[0]
      list_res.append((offset, res, order_tag))
    return list_res

  def segment_multitag(self, s) :
    '''s = "blabla" '''
    rev = self.segment_multitag_list()[::-1]
    res = s
    for offset,str_tag,order_tag in rev :
      if(order_tag == 0) :
        res = res[0:offset] + str_tag + res[offset:]
      else :
        res = res[0:offset+1] + str_tag + res[offset+1:]
    return res

  def segment_text_multitag(self, s, list_seq, list_tags) :
    self.__init__()
    for seq in list_seq :
      self.list_sequences.append(seq.list_intervals)
#    self.list_sequences = list_seq
    self.list_tags = list_tags
    return self.segment_multitag(s)

